#ifndef DIJKSTRA_H
#define DIJKSTRA_H
#include <QVector>
#include <QPair>
#include <limits>
#include <iostream>
#include <queue>
#include <geograph.h>

class Dijkstra {
public:
    Dijkstra(const GeoGraph& graph) : graph_(graph), is_cached_(false), cached_src_(-1) {}

    void calculateShortestPaths(int src) {
        if (is_cached_ && src == cached_src_) return;

        int numVertices = graph_.adjacencyList.size();
        dist_ = QVector<double>(numVertices, std::numeric_limits<double>::max());
        prev_ = QVector<int>(numVertices, -1);
        QVector<bool> visited(numVertices, false);

        dist_[src] = 0;
        using pii = QPair<double, int>;
        std::priority_queue<pii, QVector<pii>, std::greater<pii>> pq;
        pq.push(qMakePair(0.0, src));

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();
            if (visited[u]) continue;
            visited[u] = true;

            for (const QPair<int, double>& p : graph_.getAdjacencyList(u)) {
                int v = p.first;
                double weight = p.second;
                if (dist_[u] + weight < dist_[v]) {
                    dist_[v] = dist_[u] + weight;
                    prev_[v] = u;
                    pq.push(qMakePair(dist_[v], v));
                    //std::cout << v << ":" << dist_[v] << std::endl;
                }
            }
        }
        is_cached_ = true;
        cached_src_ = src;
    }

    QVector<int> findShortestPathBetween(int start_p, int end_p) {
        calculateShortestPaths(start_p);
        return reconstructPath(start_p, end_p);
    }

    double shortestPathLength(int start_p, int end_p) {
        calculateShortestPaths(start_p);
        return dist_[end_p];
    }

private:
    const GeoGraph& graph_;
    QVector<double> dist_;
    QVector<int> prev_;
    bool is_cached_;
    int cached_src_;

    QVector<int> reconstructPath(int start_p, int end_p) {
        QVector<int> path;
        for (int at = end_p; at != -1; at = prev_[at]) {
            path.push_back(at);
        }
        std::reverse(path.begin(), path.end());
        if (!path.isEmpty() && path.front() != start_p) {
            path.clear(); // Invalid path, clear and return an empty vector
        }
        std::cout << "Path from " << start_p << " to " << end_p << ": ";
        for (int vertex : path) {
            std::cout << vertex << " -> ";
        }
        std::cout << "End" << std::endl;
        return path;
    }
};

#endif // DIJKSTRA_H
